

In [1]:

    
import clique_detection as cd



In [2]:

    
num_nodes, adjacency_list = cd.parse_file_into_adjacency_list("large.dat")
graph = cd.parse_graph(num_nodes, adjacency_list)

This loads the large dolphin social network into a graph $G$.



In [3]:

    
bound = cd.bound_clique_size(graph)

Since this bound is small enough, one could check all 7-membered or smaller subgraphs of the graph $G$ to see if they were complete and get a clique. But one can do better, presumably.



In [4]:

    
clique_size = 7



In [5]:

    
valid_nodes = cd.find_possible_clique_member_nodes(clique_size, graph)



In [6]:

    
print(cd.get_cliques(clique_size, valid_nodes, graph))

[]



In [7]:

    
print(cd.find_maximum_clique(graph))









    



[(6, 9, 13, 17, 57), (18, 21, 29, 45, 51), (18, 24, 29, 45, 51)]

This was a terrible idea. Should have gone with Bronn-Kerbosch, which finds all maximal cliques. It works by starting off with 2-cliques, and expanding them, until no more cliques can be expanded. Why didn't I think of that?

Let's try Bronn-Kerbosch along with the naive bound on maximal clique size.



In [8]:

    
num_nodes2, adjacency_list2 = cd.parse_file_into_adjacency_list("small.dat")
graph2 = cd.parse_graph(num_nodes2, adjacency_list2)



In [9]:

    
small_clique = (0,1)



In [10]:

    
print(cd.get_clique_extensions(small_clique, graph2))









    



[(0, 1, 2)]



In [11]:

    
print(cd.get_two_cliques(graph2))









    



[(0, 1), (0, 2), (0, 3), (0, 5), (1, 2), (1, 4), (1, 6), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]



In [12]:

    
cd.find_maximal_cliques(graph)









    Out[12]:





{(6, 9, 13, 17, 57), (18, 21, 29, 45, 51), (18, 24, 29, 45, 51)}



In [13]:

    
%timeit cd.find_maximal_cliques(graph)









    



100 loops, best of 3: 6.7 ms per loop



In [14]:

    
%prun cd.find_maximal_cliques(graph)



In [ ]: